#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1024 * 256;
constexpr int limit = 1024 * 256;
// 33445516
constexpr auto getPrimes() {
  bool notPrime[N]{};
  array<int, 23000> primes{};
  for (int i = 2; i * i < N; ++i) {
    if (!notPrime[i]) {
      for (int j = i * i; j < N; j += i) {
        notPrime[j] = true;
      }
    }
  }
  for (int i = 2, index = 0; i < N; ++i) {
    if (!notPrime[i]) {
      primes[index++] = i;
    }
  }
  return primes;
}
constexpr auto primes = getPrimes();

vector<int> filter_primes() {
  const int n = 1e7;
  static bitset<n> not_prime;
  vector<int> primes;
  for (int i = 2; i < n; ++i) {
    if (!not_prime[i]) primes.push_back(i);
    for (auto prime: primes) {
      if (i * prime >= n) break;
      not_prime.set(i * prime);
      if (i % prime == 0) break;
    }
  }
  return primes;
}
void benchmark(const string &name, const auto &func) {
  auto start = chrono::high_resolution_clock::now();
  func();
  auto end = chrono::high_resolution_clock::now();
  auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
  cout << format("{} execution time: {} ms\n", name, duration.count());
}
int main() {
  int n = 100;
  for (int i = 0; i < n; i++) {}
  for (int i = 0; i < n; ++i) {}
  vector<int> vec;
  for (auto iter = vec.begin(); iter != vec.end(); iter++) {}
  for (auto iter = vec.begin(); iter != vec.end(); ++iter) {}
}